package com.zh.core;

/**
 * Created by zhaohui on 2019/11/6
 */
public class Fibonacci {

    // 计算斐波那契数列第n项

    // 直接递归，复杂度为O(n^2)
    public static int f1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return f1(n-1) + f1(n-2);
    }

    // 顺序计算，复杂度为O(n)
    public static int f2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int res = 1;
        int pre = 1;
        int temp = 0;
        for (int i = 3; i <= n ; i++) {
            temp = res;
            res += pre;
            pre = temp;
        }
        return res;
    }

    /**
     * 计算两个矩阵乘积
     * @param m1
     * @param m2
     * @return
     */
    public static int[][] multiplyMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m1[0].length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

    /**
     * 计算矩阵指数
     * @param m
     * @param p
     * @return
     */
    public static int[][] matrixPower(int[][] m, int p) {
        // res用来保存当前乘积的结果
        int[][] res = new int[m.length][m[0].length];
        // 把res设置为单位矩阵
        for (int i = 0; i < m.length; i++) {
            res[i][i] = 1;
        }
        int[][] temp = m;
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {
                res = multiplyMatrix(res, temp);
            }
            temp = multiplyMatrix(temp, temp);
        }
        return res;
    }

    // 使用矩阵乘法求解，复杂度为log(n)
    public static int f3(int n) {
        int[][] matrix = {{1, 1}, {1, 0}};
//        int[][] matrix2 = {{1, 1}};
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int[][] temp = matrixPower(matrix, n-2);
        return temp[0][0] + temp[0][1];
//        int[][] res = multiplyMatrix(matrix2, temp);
//        return res[0][0];
    }

    public static int s1(int n) {
        if (n == 0) {
            return 0;
        }
//        if (n == 1) {
//            return 1;
//        }
//        if (n == 2) {
//            return 2;
//        }
        if (n == 1 || n == 2) {
            return n;
        }
        return s1(n-1) + s1 (n-2);
    }

    public static int s2(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int res = 2;
        int pre = 1;
        int temp;
        for (int i = 3; i <= n; i++) {
            temp = res;
            res += pre;
            pre = temp;
        }
        return res;
    }

    public static int s3(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int[][] matrix = {{1, 1}, {1, 0}};
        int[][] res = matrixPower(matrix, n-2);
        return 2 * res[0][0] + res[1][0];
     }

     public static int c1(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        return c1(n-1) + c1(n-3);
     }

     public static int c2(int n) {
         if (n == 0) {
             return 0;
         }
         if (n == 1 || n == 2 || n == 3) {
             return n;
         }
         int res = 3;
         int pre = 2;
         int prepre = 1;
         int temp1 = 0;
         int temp2 = 0;
         for (int i = 4; i <= n; i++) {
             temp1 = res;
             temp2 = pre;
             res += prepre;
             pre = temp1;
             prepre = temp2;
         }
         return res;
     }

     public static int c3(int n) {
         if (n == 0) {
             return 0;
         }
         if (n == 1 || n == 2 || n == 3) {
             return n;
         }
        int[][] matrix = {{1, 1, 0}, {0, 0, 1}, {1, 0, 0}};
        int[][] res = matrixPower(matrix, n-3);
        return 3*res[0][0] + 2*res[1][0] + res[2][0];
     }

    public static void main(String[] args) {
        System.out.println(f1(20));
        System.out.println(f2(20));
        System.out.println(f3(20));
        System.out.println(s1(20));
        System.out.println(s2(20));
        System.out.println(s3(20));
        System.out.println(c1(20));
        System.out.println(c2(20));
        System.out.println(c3(20));
    }


}
